package org.example;

import com.sun.tools.javac.util.StringUtils;

/**
 * @author l'y'k
 * @version 1.0
 * @description: 排序算法
 * @date 2024/2/10 12:58
 */
public class Sort {

    public static void main(String[] args) {
        int[] arr = {1,23,576,9,23,66};
        selectSort(arr);
        printArr(arr);
    }

    private static void printArr(int[] a){
        for (int i =0;i<a.length;i++){
            System.out.print(a[i]);
            System.out.print(" ");
        }
        System.out.println();

    }

    /**
     * 冒泡排序
     * 最好：O(n) 最坏： O(n^2) 平均： O(n^2)
     */

    // 普通冒泡排序
    public static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {    // 外层控制循环次数
            for (int j = 0; j < a.length - i - 1; j++) { // 内层保证 a[n-i-1] 是最大的
                if (a[j] > a[j+1]) {
                    swap(a, j, j+1);
                }
            }
        }
    }



    // 冒泡排序优化1
    public static void bubbleSort2(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {    // 外层控制循环次数
            boolean hasSwap = false;
            for (int j = 0; j < a.length - i - 1; j++) { // 内层保证 a[n-i-1] 是最大的
                if (a[j] > a[j+1]) {
                    swap(a, j, j+1);
                    hasSwap = true;
                }
            }
            if(! hasSwap){
                return;
            }
        }
    }

    // 冒泡排序优化2
    public static void bubbleSort3(int[] a) {
        int lastSwapPos = a.length - 1;
        for(int i = 0; i < a.length -1; i++){
            int end = lastSwapPos;
            for(int j = 0; j < end; j++){
                if(a[j] > a[j+1]){
                    swap(a,j,j+1);
                    lastSwapPos = j;
                }
            }
        }
    }

    public static void bubbleSort4(int[] a) {
        int left = 0;
        int right = a.length - 1;

        while (left < right){
            for (int i = left; i < right; i++){
                if(a[i] > a[i+1]){
                    swap(a, i ,i+1);
                }
            }
            right -- ;

            for(int i = right; i > left; i -- ){
                if (a[i] < a[i-1]){
                    swap(a, i, i-1);
                }
            }

            left ++;

        }

    }


    /**
     * 选择排序，不稳定
     */

    public static void selectSort(int[] arr){

        for(int i = arr.length - 1; i >= 0; i--){
            int max = i;
            for(int j = 0;j<i;j++){
                if(arr[j] > arr[max]){
                    max = j;
                }
            }

            swap(arr, max, i);
        }

    }





    private static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }



}
